#pragma once

#include<iostream>

using namespace std;

int GetMidNum(int arr[], int left, int right)
{
	int mid = (left + right) / 2;
	if (arr[left] < arr[mid])
	{
		if (arr[mid] < arr[right])
		{
			return mid;
		}
		else if (arr[left] > arr[right])
		{
			return left;
		}
		else
		{
			return right;	
		}
	}
	else //arr[left] > arr[mid]
	{
		if (arr[mid] > arr[right])
		{
			return mid;
		}
		else if (arr[right] > arr[left])
		{
			return left;
		}
		else 
		{
			return right;
		}
	}
}

int Partition(int arr[], int left, int right)
{
	int mid = GetMidNum(arr, left, right);
	if (mid != left)
	{
		swap(arr[mid], arr[left]);
	}
	int key = left;
	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
		if (arr[cur] < arr[key] && ++prev != cur)
		{
			swap(arr[cur], arr[prev]);
		}
		++cur;
	}
	swap(arr[key], arr[prev]);
	key = prev;
	return key;
}

void QuickSort(int arr[], int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int key = Partition(arr, left, right);
	QuickSort(arr, left, key - 1);
	QuickSort(arr, key + 1, right);
}